package LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:21
 */
public class LRU<K,V> {
    //容量
    private int capacity;

    //当前有多少节点的统计
    private int count;

    //缓存节点
    private Map<K,Node<K,V>> nodeMap;
    private Node<K,V> head;
    private Node<K,V> tail;

    public LRU(int capacity){//初始化大小
        if (capacity < 1){
            throw new IllegalArgumentException(String.valueOf(capacity));
        }
        this.capacity = capacity;
        this.nodeMap = new HashMap<>();
        //初始化头节点和尾节点，利用哨兵模式减少判断头节点和尾节点为空的代码
        Node headNode = new Node(null,null);
        Node tailNode = new Node(null,null);
        // 初始化头节点和尾节点
        headNode.next = tailNode;
        tailNode.pre = headNode;
        this.head = headNode;
        this.tail = tailNode;
    }

    //put方法
    public void put(K key,V value){
        Node<K,V> node = nodeMap.get(key);//取得缓存？
        if (node == null){
            if (count >= capacity){
                //先移出一个节点
                removeNode();
            }
            node = new Node<>(key,value);
            //添加节点
            addNode(node);
        }else {
            //移动节点到头节点
            moveNodeToHead(node);
        }
    }

    public Node<K,V> get(K key){
        Node<K,V> node = nodeMap.get(key);
        if (node != null){
            moveNodeToHead(node);
        }
        return node;
    }

    private void moveNodeToHead(Node<K,V> node) {
        //从链表里面移除
        removeFromList(node);
        //添加节点到头部
        addToHead(node);
    }

    private void addNode(Node<K,V> node) {
        //头插
        addToHead(node);
        nodeMap.put(node.key,node);
        count++;
    }

    private void addToHead(Node<K,V> node) {
        Node next = head.next;
        next.pre = node;
        node.next = next;
        node.pre = head;
        head.next = node;
    }

    private void removeNode(){
        Node node = tail.pre;
        //从链表里面移除
        removeFromList(node);
        nodeMap.remove(node.key);
        count--;
    }

    private void removeFromList(Node<K,V> node){
        Node pre = node.pre;
        Node next = node.next;

        pre.next= next;
        next.pre = pre;

        //释放资源以便于垃圾回收
        node.next = null;
        node.pre = null;
    }
}
class Node<k, v> {
    k key;
    v value;
    Node pre;
    Node next;

    public Node(k key, v value) {
        this.key = key;
        this.value = value;
    }
}